Plasma Cash におけるコインの結合・分割

---.icon

親チェーンでの結合・分割 ＋ 両替プロバイダ

David Knott and I discussed a “merge/split” transaction where a user could point to specific coin IDs they own (by referencing outputs) and reshape them into new coin IDs that have different denominations but the same total value. This maintains the property that only specific users can be grieved (owners of those coin IDs). The transaction would require a challenge period much like the Plasma MVP exit transaction. A merge/split is invalidated under the same conditions as

kfichter：David Knott と自分は「結合・分割」トランザクションについて議論した。このトランザクションには特定のコイン ID がいくつか指定されており、総量を同じに保ったまま、それらのコインを異なる単位のいくつかの新しいコインに再形成する。この仕組みによって悲しむのは、依然として特定のユーザー（コインの保有者達）だけである。トランザクションの承認には、Plasma MVP における exit と同様の challenge 期間が必要。結合・分割は、以下のような状況下で無効化できる。

This construction would allow users to modify their coins without having to exit and deposit again.

kfichter：これによって、ユーザーは exit や再デポジットなくコインを結合・分割できる。

I also started thinking about the idea of “change providers” - users who carry a large amount of change to assist in transactions where one or both parties can’t make correct change. To illustrate:

kfichter：自分は「両替プロバイダ」というアイデアについても考え始めた。

Alice wants to send 7 ETH to Bob, but doesn’t have a 7 ETH coin. Alice has a 10 ETH coin and some smaller coins. Bob does not have a 3 ETH coin to send in return. Carol is a change provider who happens to have both a 7 ETH coin and a 3 ETH coin. Alice and Carol construct a transaction in which the following ownership transfers occur:

kfichter：Alice は 7 ETH を Bob に送りたいが、7 ETH 分のコインを保有していないとする。Alice は 10 ETH 分のコインと少量のコインを保有している。Bob もお釣りとして返却する 3 ETH 分のコインを保有していない。Carol は両替プロバイダであり、偶然 7 ETH 分のコインと 3 ETH 分のコインを保有していたとする。このとき、Alice と Carol は、以下のように保有権を移動できるようなトランザクションを構築する。

1. Alice sends a 10 ETH coin to Carol

2. Carol sends a 7 ETH coin to Bob

3. Carol sends a 3 ETH coin to Alice

4. Alice sends some small ETH coin to Carol as a fee

kfichter：

1. Alice が Carol に 10 ETH 分のコインを送る

2. Carol が Bob に 7 ETH 分のコインを送る

3. Carol が Alice に 3 ETH 分のコインを送る

4. Alice は Carol に少量のコインを送る（手数料）

This last fee component is obviously the complicating factor, as it requires Alice to have some specific small ETH coin on hand to make the transaction. In the absence of a change provider, Alice could use the merge/split transaction mentioned above to convert her 10 ETH coin into 7 ETH and 3 ETH coins to transact with Bob. However, this is significantly slower due to the challenge period.

kfichter：4 の手数料が仕組みを複雑にする要素であることは明らかである。なぜなら、Alice は手数料を支払うトランザクションをつくるための少量のコインを保有していなければならないから。両替プロバイダが不在だった場合、Alice は上記の結合・分割トランザクションを使って Bob に送るための 10 ETH 分のコインを 7 ETH 分のコインと 3 ETH 分のコインに変換してもよい。しかし、これは challenge 期間のせいで時間がかかってしまう。

---.icon

小数的な概念を使った分割 ①

You could also implement this with decimals, i.e. all coin IDs must initially end with X 0s, and we simply increment the trailing 0s until they hit some max after which they can no longer be split. In this case the coin IDs aren’t being lengthened after each tx.

kfichter：小数を使うことで実装することもできる。すなわち、全ての初期コインのトークン ID の最後に X 個の 0 がつくようにして、分割不可能になるまでこれを単純にインクリメントしていく。この場合、分割トランザクションごとにトークン ID が長くなることはない。

---.icon

小数的な概念を使った分割 ②

Every coin has a 32-byte token ID (derived from, say, the block in which it was originally deposited), and a variable-length bitstring representing the digits after the decimal point, which starts out (when the token is deposited) with length 0. I’ll call these bitstrings “telomeres” (even though technically telomeres work the opposite way).

danrobinson：（デポジットに対応する）全てのコインが、32 バイトのトークン ID と、小数点以下の桁を表す可変長なビット列を持つとし、このビット列は長さ 0 から始まる（：トークンがデポジットされたとき）とする。このビット列を「テロメア」と呼ぶこととする（正確には、テロメアは逆方向に機能するが）。

A coin can be split in two with a split transaction. In a split transaction, each of the two outputs has the same token ID as the input. Their telomeres of each are one longer than the input’s—the first output has added a 0 to the end, the second has added a 1 to the end. The split transaction specifies how much value goes into the first output and how much into the second. So a coin worth 4 ETH can be split into one worth 3 and one worth 1.

danrobinson：コインは分割トランザクションによって 2 つに分割でき、分割後の 2 つのコインは分割前と同じトークン ID を持つが、それらのテロメアは分割前よりも長くなっている。すなわち、1 つ目のコインには 0 が付加され、2 つ目のコインには 1 が付加される。分割トランザクションには、1 つ目のコインと 2 つ目のコインそれぞれにどれだけの量を割り当てるかを指定する。例えば、4 ETH の価値があるコインは 3 ETH 分と 1 ETH 分に分割できる。

The location of the split coins in the Patricia Merkle tree is as children of the location where the parent coin was.

danrobinson：Merkle Patricia tree 上において、分割後のコインは分割前のコインの子に相当する位置にある。

When you see someone attempt to withdraw a coin that shares a token ID with one of your coins, you check the closest shared ancestor. If the amount they are asserting in the withdrawal is greater than the amount that their ancestor received in that split, then they are trying to cheat, and specifically they are trying to cheat you. So you can challenge by revealing their ancestor. Since their ancestor had fewer coins than they are asserting the descendant had, you’ve proven that their coin is invalid.

danrobinson：自分のコインと同じトークン ID を持つコインが引き出されようとしている場合、最も近い祖先を確認する。引き出されようとしている量が分割前の量を超えていた場合、それは不正なので、祖先を提出することで challenge できる。祖先のコインの量が引き出されようとしている子孫のコインの量より少なかった場合、不正であることが証明できたことになる。

質問 1：引き出し時の証明について

I assume that the withdrawal of a splitted coin needs to provide the withdrawer’s claim of what each ancestor’s split amount was? So assuming you are withdrawing a coin with id X.01110, the plasma contract stores how much ether was deposited to create X, and during a withdrawal you have to specify the denominations of X.0, X.01, X.011, X.0111, and X.01110.

ldct：分割後のコインの引き出しについて、各祖先がどういう分配で分割されたのかを引き出し手が主張する必要があるのでは？つまり、トークン ID が X.01110 のコインを引き出そうとしており、Plasma コントラクトは X を生成するためにデポジットされた ETH の量を保持しているとすると、X.0 と X.01 と X.011 と X.0111 と X.01110 の量を指定する必要があるのでは？

I don’t think it needs to. The challenger can just watch to see if a withdrawal exceeds the amount they know was allocated to the ancestor, in which case they know and can prove the withdrawal is fraudulent.

danrobinson：その必要はないと思う。challenger は、引き出される量が祖先に割り当てられた量を超えていないかを確認するだけでよく、超えていた場合、その引き出しは不正であることが証明できる。

This still seems underspecified. What I am worried about is this scenario: say there are coins X.00, X.01, X.10, X.11, each with 2 eth, and I own X.00. Let’s say X.01, X.10 and X.11 are colluding. X.11 exits 2.1 eth, and I don’t notice anything wrong (since our LCA is X, and 2.1 < 8). After that confirms, X.01 and X.10 both submit withdrawals. I must be able to somehow prevent all of them from succeeding. In this case, I can prove to the contract that X.1 was worth 4 eth, and the confirmed exit of X.11 and the in-flight exit of X.10 total more than 4 eth. This does imply that I have to watch every single exit of X.something, which means that a coin with t telomeres each belonging to a separate owner the overhead is t^2, which is suboptimal.

ldct：まだよくわからない。自分が心配しているのは、以下のようなシナリオ。

前提

X.00 と X.01 と X.10 と X.11 というコインがあり、それぞれ 2 ETH

自分は X.00 を保有している

X.01 と X.10 と X.11 の保有者は共謀している

シナリオ

1. X.11 が 2.1 ETH として exit されたが、自分からしたら問題はないので気づかない

我々の LCA は X であり、2.1 < 8 なので

2. 1. が承認された後、X.01 と X.10 がともに引き出しを申請する

自分はどうにかしてこれらの引き出しを妨げることができなければならない

Dang, you’re completely right. To do it cryptoeconomically, users would need to keep track of running balances of their siblings and uncles, and store all those withdrawal transactions (only like N log N total though, I think, so not TOO bad) in case they need to reveal them to challenge something. There are maybe other ways to do it that involve tracking the balance in a Merkle sum tree on the parent chain… would have to think about the tradeoffs.

質問 2：引き出し済みコインの祖先や子孫の exit について

Another thing I assume is true in this spec: the plasma contract enforces that for al P, B, after X.P is exited X.PB cannot be exited, and after X.PB is exited X.P cannot be exited.

ldct：この仕様だと、次のことが成り立つと思う。

Plasma コントラクトは全ての P と B について以下を強制する

X.P が exit されたら X.PB は exit できない

X.PB が exit されたら X.P は exit できない

Yes, but I think this can be enforced cryptoeconomically. An attempt to spend a ancestor or descendant of a previously withdrawn coin can be challenged by revealing the withdrawal. The contract just keeps track of the remaining balance in X.

danrobinson：その通りだが、これは cryptoeconomically に強制することができると思う。過去に引き出されたコインの祖先や子孫の使用は、過去の引き出しを提出することで challenge できる。コントラクトは X の残高を追跡し続けるだけでよい。

---.icon

merged coin

I think it might be possible to support merging of arbitrary coins without any challenge/response period or activity on the parent chain, and without any significant overhead or sacrifices as far as I can see.

danrobinson：challenge 期間や親チェーン上での行動なしに、任意のコインの結合をサポートできるかもしれない。自分の想像の範囲だと、これは大きなオーバーヘッドや犠牲なしで可能。

The simple solution for splitting has already been discussed: creating new tokens that represent a piece of a previously unified token (such as by adding decimal points to its token ID). The simple solution for merging would involve creating a new token that represents a “list” of previously separate tokens. These tokens would not have to be consecutive in the Patricia Merkle tree (which we had worried might have been a constraint).

danrobinson：分割に対するシンプルな解決策は、既に議論されている。それは、もとのトークンのカケラとして新しいトークン群を生成すること（トークン ID に小数点を加えるなどして）。結合に対するシンプルな解決策には、バラバラのトークンのリストとして新しいトークンを生成することが含まれる。これらのトークンは、Merkle Patricia tree 内で連続している必要はない（我々はこれが制約になるのではないかと心配していた）。

A merge transaction lists the coins that are being merged (and provides signatures from the public keys that currently control those coins). It specifies a token ID for the new coin (or it’s deterministic, like a Merkle root of the token IDs being merged).

danrobinson：結合トランザクションには、結合されるコインが羅列され（その時点におけるそれらのコインの保有者によって署名も提供される）、新しいコインのトークン ID が指定される（もしくは、結合されるコインのトークン ID の Merkle root を採用するなど、決定的に割り当てる）。

The key is that the merge transaction needs to be included in all of the positions in the Merkle Patricia tree corresponding to the inputs being merged. As a result, a proof-of-non-spend for a coin is also a proof-of-non-merge for that coin, so this adds no overhead to proofs that don’t involve merged coins. (For merged coins, you only have to provide one chain of history—the one corresponding to the merged token ID—for their post-merge history. This is much more efficient than having to carry around and provide proofs for all of the coins throughout their entire histories.)

danrobinson：重要なのは、Merkle Patricia tree において、結合されるコイン全てに対応する位置に結合トランザクションが含まれる必要があるということである。結果、コインの proof-of-non-spend は proof-of-non-merge としても機能するので、結合されたコイン（以下、merged coin と記載する）を含まない proof のために追加されるオーバーヘッドはない（merged coin について、1 コインに関する結合後の履歴を提出するだけでよく、これは全てのコインに関する proof を持ち回して提出しなければならない場合よりも効率的である）。

Merged coins can be split using a transaction that declares that the merged coin is being split back into its individual coins, each of which inherits the public key of the merged coin. Merged coins do not have decimal places and cannot be split in the way unmerged coins are. (It is probably possible to support arbitrary combinations of merges, splits, and transfers in a single transaction, but for simplicity let’s skip that for now and assume a single transaction can only either merge unmerged coins into one, split a single merged coin into its individual coins, or transfer some coins). This split transaction only needs to be included in one place in the Merkle Patricia tree (corresponding to the token ID of the merged coin).

danrobinson：merged coin は、結合前の個々のコインへの再分割を宣言するトランザクションによって分割でき、分割されたコインは、分割前のコインの保有者が保有することになる。merged coin は小数単位を持つ必要がなく、結合によって生成されていないコインは分割できない（結合・分割・譲渡を任意に組み合わせたトランザクションもサポートできるかもしれないが、単純化するために今はスキップし、1 トランザクションは「unmerged coin の結合」「merged coin の分割」「コインの譲渡」のどれかのみを担うこととする）。分割トランザクションは、Merkle Patricia tree の 1 箇所（merged coin のトークン ID に対応する位置）に含まれるだけでよい。

An attempted withdrawal of a merged coin is similar to an attempted withdrawal of all of its coins simultaneously. I haven’t mapped out the full protocol for challenge/response, but I think it will work as long as you require that, every time a merged coin is used in an attempt, challenge or response, you must also provide the paths to the merge transaction that created that coin. Challengers can then challenge the merge transaction in much the same way they’d challenge any other transaction.

danrobinson：merged coin の引き出しは、それに含まれる全てのコインの同時引き出しと似ている。challege/response についての完全なプロトコルの詳細はまだ考えていないが、機能させることはできると思う。merged coin について challenge や response が発生する場合、それを生成した結合トランザクションへのパスも提供しなければならないようにする。challenger は、その他のトランザクションに challenge するときと同様の方法で結合トランザクションにも challenge することができる。

One might be afraid this will lead to a blow-up ok the size of history proofs for coins that have been involved in many merged. However, I thiiiiiink merged coins do not entangle the histories of the coins they merge. That is, if you are only concerned with the validity of a single coin, you don’t have to look at the histories of every coin it’s ever merged with; the coin’s history can be invalid even if it was at some point merged with a coin with invalid history. If this works, that would mean that history proofs will be linear (as they are today) at worst, and if you’re proving histories for multiple coins that have any overlap in their history it will be better than linear.

danrobinson：何度も結合に関与したコインの履歴に関する proof のサイズが肥大化してしまうのではないかという懸念はあるが、merged coin はそのパーツとなっているコインの履歴と絡み合わないのではないかな〜〜〜と思う。つまり、1 つのコインの正当性についてのみ関心がある場合、それとの結合に使われた全てのコインの履歴を確認する必要はないということ。どこかで不正な履歴を持ったコインと結合されただけでも、そのコインの履歴は不正となるだろう。これが機能した場合、履歴に関する proof のサイズは、最悪でも線形に増大する（今と同じ）ということになる。履歴に重複のある複数コインに関する履歴を証明する場合、線形な増大よりも改善するだろう。

質問：トークン ID の増加について

Sorry, I don’t follow. If two given coins are not currently merged, then the given slot in the sparse Merkle tree is blank. (It doesn’t even have to be blank—it’s just irrelevant). So it doesn’t matter any more than future deposits do.

danrobinson：自分はそうは思わない。結合されていない 2 つのコインがある場合、それらに対応する sparse Merkle tree のスロットは空（必ずしも空である必要はないが、これはあまり問題ではない）。よって、将来のデポジットより大きな問題ではない。

I think the tree would have to be extremely large if it’s sparse and contains every possible unique ID. Did you have ideas for storing the unique IDs efficiently?

kfichter：Merkle tree が sparse でユニークなトークン ID を全て含む場合、それは非常に大きくなってしまうと思う。ユニークなトークン ID を効率良く保持できるアイデアはある？

In a sparse Merkle tree most of the leaves are empty, so you can precompute them and their parents, grandparents, etc. So it’s no trouble to have a sparse Merkle tree with 2^32 elements.

---.icon

単位を固定した結合・分割

Hello I’m looking into using plasma cash for enterprise side-chains. Have you considered using fixed size coins with fixed splits ? For example the only coins that can be deposited are 80 ETH and it can only be split into halves. This way every body knows that if you try to exit a 2nd level split, it can only be worth 20ETH.

paouvrad：エンタープライズ向けのサイドチェーンとして Plasma Cash を使用することを検討している。分割の割合を固定した固定サイズのコインについては考えた？例えば、デポジットできるコインは 80 ETH だけとし、これは半分ずつにしか分割できないとする。同様に、2 段階目は 20 ETH ずつにしか分割できない。

We could also define that only 2 splits of same value can merge into a new id M1, and M1 can also merge again with another M2 of the same value. This way someone receiving a merged coin (M1M2) will use it like any other coin because it splits back into the halves M1 and M2.

Deposits of 40ETH, 20ETH … could also be accepted and quarters can be used instead of halves… all defined in plasma contract.

paouvrard：同じ値の 2 つのコインどうしのみ、新しいトークン ID：M1 のコインに結合できるとし、M1 は同じ値の M2 と結合できる。結合されたコイン（M1M2）を受け取った人は、このコインを他のコインと同様に使用できる。このコインは M1 と M2 に再分割もできる。

paouvrard：40 ETH や 20 ETH や … のデポジットも受け入れてもよいし、半分ずつの分割ではなくて四等分などにしてもよい。これらは全て Plasma コントラクトで定義される。

With this construction, coins can be merged into new ids (requires on-chain TX so that plasma is aware of it). But we could also make a protocol for easy swap of splits between users so that they can merge back to parent without paying the on chain merge fee (useful for small coin denominations). Users shouldn’t care which coin they have as long as it is of the same value.

I’m hoping we wouldn’t have to rely as much on change providers if coins can be merged and split …

paouvrard：この構成だと、コインが結合すると新しいトークン ID が付与される（Plasma が気づけるよう、オンチェーンなトランザクションが必要）。一方、ユーザー間における簡単なコイン交換のためのプロトコルをつくることもでき、そうすることでオンチェーンな手数料なしに再結合できる（小さな単位のコインにとって有用）。同じ値のコインである限り、ユーザーは自分がどのコインを保有しているかについて気にしないでよい。

paouvrad：コインが結合・分割可能であれば、両替プロバイダに大きく依存する必要がなくなる。

You mean it’s tricky to challenge because merging two splits back to their parent happens off-chain ?

Hmm the game can become very long as an attacker can challenge with an invalid split that has to be challenged…

paouvrad：2 つのコインの再結合がオフチェーンで発生するから challenge が難しいという意味？

paouvrad：ふむ。challenge される必要のある不正な分割をもってして攻撃者が challenge できるため、ゲームはとても長期間に渡ることもある。

If only parent merging is possible, an attack might be to own a very small split of each coin and prevent everybody from merging.

paouvrad：元の親への結合だけが可能であれば、an attack might be to own very small split of each coin であり、誰もが結合できないようにすることもできる。

I’ve found myself to be pathologically overoptimistic about the workability of various splitting and merging schemes, but I definitely think it’s possible to do equal-value splits and sibling merges without significantly changing the Plasma Cash exit game.

danrobinson：自分が様々な分割・結合スキームの実現にあたり、過度に最適化しようとしていることに気づいた。Plasma Cash の exit ゲームに大きな変更を加えずに等分な分割と兄弟の結合を行うことは間違いなく可能だと思う。

If someone attempts to exit an outdated splitted or merged coin, you can reveal a subsequent spend, merge, or split of that coin, just like you can with a normal coin.

danrobinson：分割された or 結合された古いコインが引き出されようとしている場合、通常のコインと同様にそのコインに関する後続の使用 or 結合 or 分割を公開することができる。

If someone attempts to reveal an invalid coin in your coin’s future (i.e. if the Plasma Cash chain operator has gone byzantine), you can reveal your currently held coin and challenge them to provide the subsequent spend, merge, or split of that coin.

danrobinson：不正な履歴を加えて生まれたコインが公開しようとした場合（すなわち、子チェーンのオペレータがビザンチンだった場合）、後続の使用 or 結合 or 分割を提出するために、現在保有しているコインを公開して challenge できる。

The difficulties come when you start having non-equal splits and (especially) non-sibling merges.

danrobinson：複雑なのは、等分でない分割や（特に）兄弟でないコインとの結合が発生し始めた場合。

I might be wrong but only having equal splits seems ok. If merging is only done with equal value coins, when you split a merged coin again, users always get the same result, looks more like cash with fixed denominations… Also, different value split coins prevent convenient coin swapping for merging back to parent.

paouvrad：間違っているかもしれないが、等分な分割だけなら大丈夫だと思う。同じ値のコインどうししか結合できない場合、結合されたコインを再分割する際、ユーザーは常に同じ結果を得られる。これは単位の固定された現金と同じようなもの。また、等分でない分割は、再結合のための便利なコイン交換を妨げる。

Non-sibling merges can only be done with an on-chain transaction, otherwise a byzantine chain can withdraw new random coin ids and we have data availability problem like in plasma MVP. However if exiting non-sibling merges requires specifying input splits then we can skip the on-chain merging transaction as data is made available to exit and input splits can be challenged (with merges of merges both the splits and intermediate merges should be specified to exit the parent merge)

paouvrad：兄弟でないコインの結合はオンチェーンなトランザクションによってのみ可能。さもなければ、ビザンチンなチェーンは新しい適当なコインを引き出せてしまうし、Plasma MVP のようなデータの availability に関する問題も発生する。しかし、兄弟でないコインの結合によって生まれたコインの exit に結合するコインの指定が必要な場合、データは exit できるように available になるし、結合するコインには challenge できるので、オンチェーンな結合トランザクションをスキップできる（with merges of merges both the splits and intermediate merges should be specified to exit the parent merge）。

If we have predetermined coin and split values with free sibling merges and cheap on-chain/free merging to new ids, I feel this is good enough to work… no ? At this point I don’t see the benefit of custom split values ~

paouvrad：固定サイズのコイン、分割の割合の固定、兄弟どうしの自由な結合、安価でオンチェーンな or 自由な結合による新しいトークン ID を持ったコイン生成。これらは十分機能すると思うけど、間違ってる？自分には自由な割合で分割するメリットが分からない。